package demo1;

import java.util.Stack;
//题目4 ：栈的压入，弹出序列
class Solution2{
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i< pushV.length;i++) {
            stack.push(pushV[i]);
            while(!stack.empty() && j < popV.length &&
                    stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }

        return stack.empty();
    }


}




















//题目3：逆波兰表达式求值
//中缀表达式转换成后缀表达式

//遍历后缀表达式，将遇到的数压入栈中， 当遇到运算符时，则进行两次出栈，获取的操作数进行运算，然后再将结果压入栈中
//以此类推。
//总结：        1 . 字符串形式的运算符不能直接转换成运算符
                     //2. 后缀表达式先进栈的是左操作数，后进栈的是右操作数，当我们需要出栈时，第一次获取栈顶元素是右操作数
                    //第二次是左操作数
class Solution {
    public int evalRPN(String[] tokens) {
        //创建一个栈，创建栈时不需要考虑栈的空间大小
        Stack<Integer> stack = new Stack<>();
        //采用foreach进行遍历栈
        for (String str : tokens) {
            if (!isOperator(str)) {
                int a = Integer.parseInt(str);
                stack.push(a);
            } else {
                //这里有问题了
                int val2 = stack.pop();
                int val1 = stack.pop();
                //如果为运算符
                switch (str) {
                    case "+" : stack.push(val1 + val2);
                        break;
                    case "-" :  stack.push(val1 - val2);
                         break;
                    case "*" : stack.push(val1 * val2);
                         break;
                    case "/" : stack.push(val1 / val2);
                        break;
                }
            }
        }
        return stack.peek();
    }


 public boolean isOperator(String str){
        if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
            return true;
        }
        return false;
        }






}

//题目2 ：括号的匹配问题，
//思想1：遍历整个字符串，遇到左括号则装入栈中，遇到到右括号时，与栈顶的左括号进行比较
//如果相匹配，则继续循环，如果不匹配则返回false



//总结：在涉及栈的使用，压栈与获取栈顶元素时，首先考虑栈是否为空的问题，不需要考虑栈是否已满的情况
class Solution1 {
    public boolean isValid(String s) {
        Stack <Character> stack = new Stack<>();
       //采用for循环，这样可以找到字符串中的字符
        for(int i =0;i<s.length();i++) {
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') {
                //问题，java提供的栈是否需要手动扩容？
                stack.push(ch);
            } else {
                //如果是右括号的内容
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char ch2 = stack.peek();   //当获取栈顶元素时，栈可能为空
                    //栈区不能为空
                    if (((ch == '}' && ch2 == '{') || (ch == ']' && ch2 == '[') || (ch == ')' && ch2 == '('))) {
                        //说明匹配，
                        //将栈顶的元素去除
                        stack.pop();
                    } else {
                        //如果不匹配，情况1 如果栈中还没有左括号，则一定不匹配，
                        return false;
                    }
                }
            }
        }
         // 如果栈表为空，说明匹配完毕
        if(stack.isEmpty()){
            return true;
        }
       return false;
    }
}

public class Test {
    public static void main(String[] args) {
        //2 . 括号匹配问题
   /* Solution solution = new Solution();
        System.out.println(solution.isValid("()"));*/
     // 3.

    }
}

/*


    public static void main2(String[] args) {
        //栈的算法题：
        // 1 ：逆序打印单链表
           //将单链表放入栈中，再依次遍历
        //创建一个栈
      /*  Stack<Node>stack = new Stack<Node>();
        //指定链表存入栈中
        Node cur = head;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        //最后再打印链表
        //是直接逆序链表，还是打印链表中的元素？
        //打印链表中的元素
        //当栈不为空时
        while (!stack.isEmpty()){  //当栈不为空时
            System.out.println(stack.pop().data + " ");
        }
*/
















/*

    }



    public static void main1(String[] args) {
        // 任务1 ：
        // 实现栈，
        //  任务 2  将栈的几个算法题写一遍，熟悉栈的使用
        //  任务3 : 写一篇博客
    }



}
*/
